package lc;
import java.util.*;
import java.util.stream.Collectors;

import org.junit.*;
public class Ex128 {

    /**
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
     */

    class Solution {
        public int longestConsecutive(int[] nums) {
            if (nums.length <= 1) return nums.length;
            UnionFindSet ufs = new UnionFindSet(nums);
            Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
            int res = 1;
            for (int n: nums) {
                if (set.contains(n + 1)) {
                    if (!ufs.isConnect(n, n + 1)) {
                        int weight = ufs.union(n, n + 1);
                        res = Math.max(weight, res);
                    }
                }
            }
            return res;
        }
    }

    class UnionFindSet {
        Map<Integer, Integer> parent;
        Map<Integer, Integer> weight;

        public UnionFindSet(int[] nums) {
            parent = new HashMap<>();
            weight = new HashMap<>();
            for (int n : nums) {
                parent.put(n, n);
                weight.put(n, 1);
            }
        }

        public int find(int n) {
            int p;
            if ((p = parent.get(n)) == n) {
                return n;
            }
            int r = find(p);
            parent.put(n, r);
            return r;
        }

        public int union(int n1, int n2) {
            int r1 = find(n1), r2 = find(n2), w1 = weight.get(r1), w2 = weight.get(r2);
            if (r1 == r2) {
                return w1;
            } else if (r1 < r2) {
                parent.put(r2, r1);
                weight.put(r1, w1 + w2);
                return w1 + w2;
            } else {
                parent.put(r1, r2);
                weight.put(r2, w1 + w2);
                return w1 + w2;
            }
        }

        public boolean isConnect(int n1, int n2) {
            return find(n1) == find(n2);
        }

    }
}
